// https://www.lintcode.com/problem/decode-string/description

class Solution {
public:
    /**
     * @param s: an expression includes numbers, letters and brackets
     * @return: a string
     */
    
    // 法一：递归
    // string getString(string &s) {
    //     string result = "";
    //     int i = 0;
    //     int left = 0;
    //     int right = 0; //要记录对应的括号
    //     while (i < s.length())
    //     {
    //         cout << result << endl;
    //         string digit = "";
    //         while (i < s.length() && s[i] >= '0' && s[i] <= '9')
    //         {
    //             digit += s[i++];
    //         }
    //         if (digit != "") 
    //         {
    //             int num = stoi(digit); 
    //             i++;
    //             string substr = "";
    //             left++;
    //             while (left != right)
    //             {
    //                 substr += s[i++];
    //                 if (s[i] == '[') left++;
    //                 if (s[i] == ']') right++;
    //             }
    //             string tmp = getString(substr);
    //             for (int j = 0; j < num; ++j)
    //             {
    //                 result += tmp;
    //             }
    //             i++; //注意
    //         }
    //         else
    //         {
    //             while (i < s.length() && s[i] > '9')
    //             {
    //                 result += s[i++];
    //             }
    //         }
    //     }
    //     return result;
    // } 
    
    // string expressionExpand(string &s) {
    //     return getString(s);
    // }
    
    
    // 法二：非递归
    string getString(string &s) {
       stack<char> charStack;
       int i = 0;
       string result = "";
       while (i < s.length())
       {
           if (s[i] >= 'a' && s[i] <= 'z' || (s[i] >= 'A' && s[i] <= 'Z'))
           {
               charStack.push(s[i++]);
               continue;
           }
           while (s[i] != ']') 
           {
               charStack.push(s[i++]);
           }
           string tmp = "";
           while (charStack.top() != '[')
           {
               tmp += charStack.top();
               charStack.pop();
           }
           charStack.pop();
           string digit = "";
           while (!charStack.empty() && (charStack.top() >= '0' && charStack.top() <= '9')) //只要是在内部自加自减的都要注意判断
           {
               digit += charStack.top();
               charStack.pop();
           }
           reverse(digit.begin(), digit.end());
           reverse(tmp.begin(), tmp.end());
           int num = stoi(digit);
           for (int j = 0; j < num; ++j)
           {
                for (char t: tmp)
                    charStack.push(t);
           }
           i++;
       }
       while (!charStack.empty())
       {
           result += charStack.top();
           charStack.pop();
       }
       reverse(result.begin(), result.end());
       return result;
    } 
    
    string expressionExpand(string &s) {
        return getString(s);
    }
};